package 滑动窗口;

public class No992K个不同整数的子数组 {

    /**
     * 给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，
     * 则称 A 的这个连续、不一定独立的子数组为好子数组。
     * （例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。）
     * 返回 A 中好子数组的数目。
     *
     * 示例 1：
     * 输入：A = [1,2,1,2,3], K = 2
     * 输出：7
     * 解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
     * 示例 2：
     * 输入：A = [1,2,1,3,4], K = 3
     * 输出：3
     * 解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].
     *  
     * 提示：
     * 1 <= A.length <= 20000
     * 1 <= A[i] <= A.length
     * 1 <= K <= A.length
     */

    //恰好转为最多是关键,然后就可以用窗口+frep[]来愉快的进行判断了
    public int subarraysWithKDistinct(int[] A, int K) {
        return mostSubarraysWithKDistinct(A,K)-mostSubarraysWithKDistinct(A,K-1);
    }

    private int mostSubarraysWithKDistinct(int[] A,int k){

        int[] frep=new int[A.length+1];//提示可得K的大小最大为K.length
        int left=0;
        int right=0;
        int count=0;
        int res=0;

        while (right<A.length){

            int rightNum=A[right];
            right++;
            if(frep[rightNum]==0){
                count++;
            }
            frep[rightNum]++;
            //如果count多了,就要让count变成k
            //吐出,直到count=k为止
            while (count>k){
                int leftNum=A[left];
                if(frep[leftNum]==1){
                    count--;
                }
                frep[leftNum]--;
                left++;
            }
            res+=right-left;
        }

        return res;
    }

    public static void main(String[] args) {
        No992K个不同整数的子数组 n=new No992K个不同整数的子数组();
        int[] arr={1,2,1,2,3};
        int result = n.subarraysWithKDistinct(arr, 2);
        System.out.println(result);
    }

}
